package avl;

//AvlTree class
//
//CONSTRUCTION: with no initializer
//
//******************PUBLIC OPERATIONS*********************
//void insert( x )       --> Insert x
//void remove( x )       --> Remove x (unimplemented)
//boolean contains( x )  --> Return true if x is present
//Comparable findMin( )  --> Return smallest item
//Comparable findMax( )  --> Return largest item
//boolean isEmpty( )     --> Return true if empty; else false
//void makeEmpty( )      --> Remove all items
//void printTree( )      --> Print tree in sorted order
//******************ERRORS********************************
//Throws UnderflowException as appropriate

/**
* Implements an AVL tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class AvlTree<AnyType extends Comparable<? super AnyType>>
{
 /**
  * Construct the tree.
  */
 public AvlTree( )
 {
     root = null;
 }

 /**
  * Insert into the tree; duplicates are ignored.
  * @param x the item to insert.
  */
 public void insert( AnyType x )
 {
     root = insert( x, root );
 }

 /**
  * Remove from the tree. Nothing is done if x is not found.
  * @param x the item to remove.
  */
 public void remove( AnyType x )
 {
     System.out.println( "Sorry, remove unimplemented" );
 }

 /**
  * Find the smallest item in the tree.
  * @return smallest item or null if empty.
  */
 public AnyType findMin( )
 {
	if( isEmpty( ) )
		try {
			throw new Exception( );
		} catch (Exception e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
     return findMin( root ).element;
 }

 /**
  * Find the largest item in the tree.
  * @return the largest item of null if empty.
 * @throws Exception 
  */
 public AnyType findMax( ) throws Exception
 {
	if( isEmpty( ) )
		     throw new Exception( );
     return findMax( root ).element;
 }

 /**
  * Find an item in the tree.
  * @param x the item to search for.
  * @return true if x is found.
  */
 public boolean contains( AnyType x )
 {
     return contains( x, root );
 }

 /**
  * Make the tree logically empty.
  */
 public void makeEmpty( )
 {
     root = null;
 }

 /**
  * Test if the tree is logically empty.
  * @return true if empty, false otherwise.
  */
 public boolean isEmpty( )
 {
     return root == null;
 }

 /**
  * Print the tree contents in sorted order.
  */
 public void printTree( )
 {
     if( isEmpty( ) )
         System.out.println( "Empty tree" );
     else
         printTree( root );
 }
 
 /**
  * Internal method to insert into a subtree.
  * @param x the item to insert.
  * @param t the node that roots the subtree.
  * @return the new root of the subtree.
  */
 private AvlNode<AnyType> insert( AnyType x, AvlNode<AnyType> t )
 {
     if( t == null )
         return new AvlNode<AnyType>( x, null, null );
		   
			int compareResult = x.compareTo( t.element );
			    
     if( compareResult < 0 )
     {
         t.left = insert( x, t.left );
         if( height( t.left ) - height( t.right ) == 2 )
             if( x.compareTo( t.left.element ) < 0 )
                 t = rotateWithLeftChild( t );
             else
                 t = doubleWithLeftChild( t );
     }
     else if( compareResult > 0 )
     {
         t.right = insert( x, t.right );
         if( height( t.right ) - height( t.left ) == 2 )
             if( x.compareTo( t.right.element ) > 0 )
                 t = rotateWithRightChild( t );
             else
                 t = doubleWithRightChild( t );
     }
     else
         ;  // Duplicate; do nothing
     t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
     return t;
 }

 /**
  * Internal method to find the smallest item in a subtree.
  * @param t the node that roots the tree.
  * @return node containing the smallest item.
  */
 private AvlNode<AnyType> findMin( AvlNode<AnyType> t )
 {
     if( t == null )
         return t;

     while( t.left != null )
         t = t.left;
     return t;
 }

 /**
  * Internal method to find the largest item in a subtree.
  * @param t the node that roots the tree.
  * @return node containing the largest item.
  */
 private AvlNode<AnyType> findMax( AvlNode<AnyType> t )
 {
     if( t == null )
         return t;

     while( t.right != null )
         t = t.right;
     return t;
 }

 /**
  * Internal method to find an item in a subtree.
  * @param x is item to search for.
  * @param t the node that roots the tree.
  * @return true if x is found in subtree.
  */
 private boolean contains( AnyType x, AvlNode<AnyType> t )
 {
     while( t != null )
	       {
			int compareResult = x.compareTo( t.element );
					  
         if( compareResult < 0 )
             t = t.left;
         else if( compareResult > 0 )
             t = t.right;
         else
             return true;    // Match
		       }

     return false;   // No match
 }

 /**
  * Internal method to print a subtree in sorted order.
  * @param t the node that roots the tree.
  */
 private void printTree( AvlNode<AnyType> t )
 {
     if( t != null )
     {
         printTree( t.left );
         System.out.println( t.element );
         printTree( t.right );
     }
 }

 /**
  * Return the height of node t, or -1, if null.
  */
 private int height( AvlNode<AnyType> t )
 {
     return t == null ? -1 : t.height;
 }

 /**
  * Rotate binary tree node with left child.
  * For AVL trees, this is a single rotation for case 1.
  * Update heights, then return new root.
  */
 private AvlNode<AnyType> rotateWithLeftChild( AvlNode<AnyType> k2 )
 {
     AvlNode<AnyType> k1 = k2.left;
     k2.left = k1.right;
     k1.right = k2;
     k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
     k1.height = Math.max( height( k1.left ), k2.height ) + 1;
     return k1;
 }

 /**
  * Rotate binary tree node with right child.
  * For AVL trees, this is a single rotation for case 4.
  * Update heights, then return new root.
  */
 private AvlNode<AnyType> rotateWithRightChild( AvlNode<AnyType> k1 )
 {
     AvlNode<AnyType> k2 = k1.right;
     k1.right = k2.left;
     k2.left = k1;
     k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
     k2.height = Math.max( height( k2.right ), k1.height ) + 1;
     return k2;
 }

 /**
  * Double rotate binary tree node: first left child
  * with its right child; then node k3 with new left child.
  * For AVL trees, this is a double rotation for case 2.
  * Update heights, then return new root.
  */
 private AvlNode<AnyType> doubleWithLeftChild( AvlNode<AnyType> k3 )
 {
     k3.left = rotateWithRightChild( k3.left );
     return rotateWithLeftChild( k3 );
 }

 /**
  * Double rotate binary tree node: first right child
  * with its left child; then node k1 with new right child.
  * For AVL trees, this is a double rotation for case 3.
  * Update heights, then return new root.
  */
 private AvlNode<AnyType> doubleWithRightChild( AvlNode<AnyType> k1 )
 {
     k1.right = rotateWithLeftChild( k1.right );
     return rotateWithRightChild( k1 );
 }

 private static class AvlNode<AnyType>
 {
         AvlNode( AnyType theElement, AvlNode<AnyType> lt, AvlNode<AnyType> rt )
     {
         element  = theElement;
         left     = lt;
         right    = rt;
         height   = 0;
     }

     AnyType           element;      // The data in the node
     AvlNode<AnyType>  left;         // Left child
     AvlNode<AnyType>  right;        // Right child
     int               height;       // Height
 }

   /** The tree root. */
 private AvlNode<AnyType> root;


     // Test program
 public static void main( String [ ] args ){
    AvlTree<Integer> t = new AvlTree<Integer>( );

     for(int x=0;x<99;x= x+2){
    	 t.insert(x);
     }
     t.printTree();
}
}
